/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
/* 
方法思路
预处理：首先检查 s1 和 s2 的长度之和是否等于 s3 的长度，如果不相等，直接返回 false。
动态规划数组：创建一个二维布尔数组 dp，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符是否能交错组成 s3 的前 i+j 个字符。
初始化：
dp[0][0] 为 true，因为空字符串可以由两个空字符串交错组成。
初始化第一行 dp[0][j]，表示 s1 为空时，s2 的前 j 个字符是否能组成 s3 的前 j 个字符。
初始化第一列 dp[i][0]，表示 s2 为空时，s1 的前 i 个字符是否能组成 s3 的前 i 个字符。
状态转移方程：对于每个 i > 0 和 j > 0，dp[i][j] 为 true 的条件是：
dp[i-1][j] 为 true 且 s1 的第 i 个字符等于 s3 的第 i+j 个字符，或者
dp[i][j-1] 为 true 且 s2 的第 j 个字符等于 s3 的第 i+j 个字符。
结果：dp[m][n] 即为最终结果，其中 m 和 n 分别是 s1 和 s2 的长度。

代码解释
预处理：检查 s1 和 s2 的长度之和是否等于 s3 的长度，若不相等则直接返回 false。
动态规划数组初始化：创建一个 (m+1) x (n+1) 的二维数组 dp，其中 dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否交错组成 s3 的前 i+j 个字符。
边界条件处理：
dp[0][0] 初始化为 true，表示空字符串可以由两个空字符串交错组成。
初始化第一行和第一列，分别处理 s1 为空和 s2 为空的情况。
状态转移：遍历每个可能的 i 和 j，根据当前字符是否匹配以及之前的状态更新 dp[i][j]。
结果返回：返回 dp[m][n]，即整个字符串是否能被交错组成。
*/

var isInterleave = function (s1, s2, s3) {
  const m = s1.length;
  const n = s2.length;
  const k = s3.length;

  if (m + n !== k) return false;

  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));

  // 初始化dp[0][0]
  dp[0][0] = true;

  // 初始化第一行：s1为空的情况
  for (let j = 1; j <= n; j++) {
    dp[0][j] = dp[0][j - 1] && s2[j - 1] === s3[j - 1];
  }

  // 初始化第一列：s2为空的情况
  for (let i = 1; i <= m; i++) {
    dp[i][0] = dp[i - 1][0] && s1[i - 1] === s3[i - 1];
  }

  // 填充dp数组
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      dp[i][j] = (dp[i - 1][j] && s1[i - 1] === s3[i + j - 1]) ||
        (dp[i][j - 1] && s2[j - 1] === s3[i + j - 1]);
    }
  }

  return dp[m][n];
};